/*
 * automato.c
 *
 *  Created on: 05/06/2012
 *      Author: annibal
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "automato.h"
#include "leitura.h"

/*
 * Cria um estado no endereço selecionado
 */
void criaEstado(Estado *endereco, char* nome, int final) {
	Estado estado;
	strcpy(estado.nome, nome);
	estado.final = final;
	*endereco = estado;
}

/* Cria o autômato finito a partir do arquivo de especificações */
void criaAutomato(Automato *M, FILE *espec) {
	criaEstados(M, espec);
	M->estadoInicial = M->estados;

	geraAlfabeto(M, espec);

	criaTransicoes(M, espec);

	M->leitor = NULL;
}

/* Cria o vetor que guarda o conjunto de estados do AF */
void criaEstados(Automato *M, FILE *espec) {
	int i, j, final;
	char *nomeEstado;

	/* Lê o número de estados do AF */
	M->numEstados = leInteiro(espec);
	M->estados = (Estado*) malloc(M->numEstados * sizeof(Estado));

	/*
	 * Leitura do nome dos estados e geração dos seus parâmetros para
	 * criação (nome e indicação de estado final)
	 */
	for (i = 0; i < M->numEstados; i++) {
		nomeEstado = leString(espec);

		if (nomeEstado[0] == '*') {
			final = TRUE;
			for (j = 0; j < strlen(nomeEstado); j++) {
				nomeEstado[j] = nomeEstado[j + 1];
			}
		} else {
			final = FALSE;
		}

		criaEstado(M->estados + i, nomeEstado, final);
		free(nomeEstado);
	}
}

/* Identifica o alfabeto do sobre o qual o AF trabalha */
void geraAlfabeto(Automato *M, FILE *espec) {
	int i;
	char simbolo;

	/* Lê o tamanho do alfabeto */
	M->tamAlfabeto = leInteiro(espec);
	M->alfabeto = (char*) malloc(M->tamAlfabeto * sizeof(char));

	for (i = 0; i < M->tamAlfabeto; i++) {
		simbolo = leCaractere(espec);
		M->alfabeto[i] = simbolo;
	}
}

/* Cria as transições do autômato */
void criaTransicoes(Automato *M, FILE *espec) {
	int i, fim = FALSE;

	M->transicoes = (Estado***) malloc(M->numEstados * sizeof(Estado**));
	for (i = 0; i < M->numEstados; i++) {
		M->transicoes[i] = (Estado**) calloc((M->tamAlfabeto + 1),
				sizeof(Estado*));
	}

	/* Lê o arquivo até o fim, montando as transições do AF */
	while (fim == FALSE) {
		fim = adicionaTransicao(M, espec);
	}
}

/* Adiciona uma transição à tabela de transições do AF. */
int adicionaTransicao(Automato *M, FILE *espec) {
	int i, j, k, achou = FALSE, fimArquivo = FALSE;
	char *nomeAtual = NULL, *nomeProximo = NULL, caractere;
	Estado *proximo = NULL;

	nomeAtual = leString(espec);

	/* Verifica se o estado de origem da transição é válido */
	if (nomeAtual != NULL) {
		for (i = 0; i < M->numEstados && achou == FALSE; i++) {
			if (strcmp(M->estados[i].nome, nomeAtual) == 0) {
				achou = TRUE;
				free(nomeAtual);
			}
		}
	} else {
		fimArquivo = TRUE;
	}

	if (fimArquivo == FALSE) {
		caractere = leCaractere(espec);
		nomeProximo = leString(espec);

		/* Verifica se o estado de destino da transição é válido */
		for (k = 0; k < M->numEstados && proximo == NULL; k++) {
			if (strcmp(M->estados[k].nome, nomeProximo) == 0) {
				proximo = M->estados + k;
				free(nomeProximo);
			}
		}

		/* Verifica se o simbolo da transicao pertence ao alfabeto */
		achou = FALSE;
		for (j = 0; j < M->tamAlfabeto && achou == FALSE; j++) {
			if (M->alfabeto[j] == caractere) {
				achou = TRUE;
			}
		}

		/* Caso o símbolo não pertença ao alfabeto, a transição é adicionada à coluna "outros" */
		if (achou == TRUE) {
			M->transicoes[i - 1][j - 1] = proximo;
		} else {
			M->transicoes[i - 1][M->tamAlfabeto] = proximo;
		}
	}

	return fimArquivo;
}

/*
 * Verifica se uma cadeia é aceita pelo autômato
 *
 * Retorno: 1 se a cadeia for aceita, 0 caso contrário
 */
int analisaCadeia(Automato *M, char *cadeia, FILE *saida) {
	int fim = FALSE, semTransicao = FALSE;

	M->estadoAtual = M->estadoInicial;

	/* Lê o arquivo até o final */
	while (fim == FALSE) {
		fprintf(saida, "\n%10s ", M->estadoAtual->nome);
		/*
		 * Se o leitor conter o caractere nulo, utilizado para simbolizar a cadeia nula,
		 * a análise termina.
		 */
		if (*(M->leitor) == '\0') {
			fprintf(saida, "%10s", "(null)");
			fim = TRUE;
		} else {
			fprintf(saida, "%10c ", *(M->leitor));
			/*
			 * Busca uma transição dado o estado atual e o símbolo lido; caso
			 * não exista uma, a análise termina e a cadeia é rejeitada
			 */
			if (analisaSimbolo(M, saida) == 0) {
				semTransicao = TRUE;
				fim = TRUE;
			}
			(M->leitor)++;
		}
	}

	if (M->estadoAtual->final == TRUE && semTransicao == FALSE) {
		return TRUE;
	}

	return FALSE;
}

/*
 * Verifica se, dado o estado atual do autômato, existe uma transição
 * possível para um determinado símbolo
 *
 * Retorno: 1 se existir uma transição, 0 caso contrário
 */
int analisaSimbolo(Automato *M, FILE *saida) {
	Estado *proximo;

	proximo = buscaTransicao(M);
	fprintf(saida, "%10s", proximo->nome);

	if (proximo != NULL) {
		M->estadoAtual = proximo;
		return TRUE;
	}

	return FALSE;
}

/* Procura por uma transição na tabela de transições */
Estado* buscaTransicao(Automato *M) {
	int i, j, achou = FALSE;

	for (i = 0; i < M->numEstados && achou == FALSE; i++) {
		if (M->estados + i == M->estadoAtual) {
			achou = TRUE;
		}
	}

	achou = FALSE;
	for (j = 0; j < M->tamAlfabeto && achou == FALSE; j++) {
		if (M->alfabeto[j] == *(M->leitor)) {
			achou = TRUE;
		}
	}

	if (achou == TRUE) {
		return M->transicoes[i - 1][j - 1];
	} else {
		return M->transicoes[i - 1][j];
	}
}
